`
https://leetcode.cn/problems/longest-common-subsequence/
`

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function (text1, text2) {
  const m = text1.length, n = text2.length

  // 记录已计算的结果
  const memo = Array.from({ length: m }, () => new Array(n).fill(-1))

  // 定义：计算 s1[i..] 和 s2[j..] 的最长公共子序列长度
  function dp(i, j) {
    // 有一个字符串遍历完， 另一个就不需要继续遍历了
    if (i === m || j === n) {
      return 0
    }

    // 如果已经计算过了，直接从缓存拿结果
    if (memo[i][j] !== -1) {
      return memo[i][j]
    }

    // 当前两个字符相同，加入 lcs
    if (text1[i] === text2[j]) {
      memo[i][j] = dp(i + 1, j + 1) + 1
    } else {
      memo[i][j] = Math.max(
        // text1[i] 不在 lcs 内
        dp(i + 1, j),
        // text2[j] 不在 lcs 内
        dp(i, j + 1)
      )
    }

    return memo[i][j]
  }

  return dp(0, 0)
};